package com.yuren.codecrushlearn.Q5400;

/**
 * Created with Intellij IDEA.
 * Description:
 *
 * @author 10204
 * @date 2025-06-06 01:18
 */
public class Q5423 {

    /**
     * solveKnapsack dp 滚动数组
     * 简化思路：
     * 1.每个物品有两种选择，不装入背包 / 尝试装入背包，则尝试枚举所有情况后检查是否符合题意，但时间复杂度为 O(2^n)，超时
     * 2.考虑 weights 的区间 [0,i] 的子序列可能的重量，通过记忆化来优化重复的计算
     * 定义状态：f(i,w) 表示前 i 个物品，可能装入背包的总重量为 w
     * 状态转移：对于第 i 个物品
     * 选择不装入背包时：f(i,w) = f(i-1,w)
     * 选择尝试装入背包时：f(i,w) = f(i-1, w-weights[i])，条件为 weights[i] <= w
     * 两者任一满足，则 f(i,w) = true
     * 3.将记忆化搜索，翻译为递推
     * 同时，f(i) 的状态只与 f(i-1) 有关，则简化为滚动数组
     * 但需要倒序遍历，防止较小的 i 在 w-weights[i] 操作后更新数据，影响 f(i) 的计算
     * 时间复杂度：O(w*n)
     * 空间复杂度：O(w)
     */
    public int solveKnapsack(int w, int n, int[] weights) {
        int[] dp = new int[w + 1];
        dp[0] = 1;
        for (int v : weights) {
            // 倒序
            for (int i = w; i >= v; i--) {
                dp[i] += dp[i - v];
            }
        }
        return dp[w];
    }
}
